package com.ShangGuiGu.sortAlgorithm.交换排序.冒泡排序;

import java.util.Date;

/**
 * @auther zsj
 * @Date 2022/2/12
 * 冒泡排序算法
 * <p>
 * 就是在循环中将数组中或者集合中的数据进行位置的交换
 **/
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 9, -1, 10, -2};
        Date date = new Date();
        int[] result = BubbleSortMethod(arr);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + ",");
        }
    }

    /*
    时间复杂度  O（n^2）
     */
    public static int[] BubbleSortMethod(int[] numbers) {
        /**
         * 这个数组有多少个数就进行多少次的循环，每次都是将最大的气泡推向最后一个
         * 所以每次的循环都需要最少减少，因为判断过的不需要再次进行判断
         * 所以我们需要两层for循环进行封装,第二层for循环来进行次数的递减
         * 最终我们还需要避免多余的判断，有时候数组可能已经循环了一次之后已经是有序的了，但是我们的程序依然继续判断
         * 所以我们只需要写一个flag进行条件的筛选并break即可
         */
        //数组长度-1 避免下标越界
        int temp = 0;//中转盒子
        boolean flag = false; //是否进行了数组元素的交换
        for (int i = 0; i < numbers.length - 1; i++) {
            for (int j = 0; j < numbers.length - 1 - i; j++) {
                if (numbers[j] > numbers[j+1]){
                    flag =true;
                    //调换位置
                    temp = numbers[j];
                    numbers[j] = numbers[j+1];
                    numbers[j+1] =temp;
                }
            }
            if (!flag){
                break;
            }else {
                flag = false;
            }

        }

        return numbers;
    }
}
